class Solution
{
public:
    int lengthOfLIS(vector<int> &nums, int k)
    {
    }

    int LIS_Dp(vector<int> &nums, int k)
    {
        // 时间复杂度 O(n^2), 会超时
        int n = nums.size();
        vector<int> maxIncSubLenDp(n, 1);
        for (int i = 1; i < n; ++i)
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if ((nums[i] > nums[j]) && (nums[i] - nums[j] <= k))
                {
                    maxIncSubLenDp[i] = max(maxIncSubLenDp[i], 1 + maxIncSubLenDp[j]);
                }
                // if (maxIncSubLenDp[i] > j)
                // {
                //     break;
                // }
            }
        }
        return *max_element(maxIncSubLenDp.begin(), maxIncSubLenDp.end());
    }
};